The invention relates to a color barcode symbology that can be accurately decoded despite severe distortions, misreads or altered symbols. More particularly, the present invention relates to a color transition barcode having linear growth properties designed to resist the single or combined effects of: scaling distortions, perspective distortions, shear distortions and wave distortions of both the uniform type and non-uniform type distributed across the barcode's vertical or horizontal axis. The color barcode symbology of the present invention is also resistant to missing symbols and altered symbols while offering, high security, error checking, and double error correcting capability.
There are three major classification of barcodes: one-dimensional, two-dimensional, and transition codes.
One-dimensional codes are typically a linear array of elements that are either printed directly on an object or on labels that are affixed to the object. As shown in FIG. 1, barcode elements typically are comprised of parallel bars and spaces, with bars of varying widths representing strings binary ones and spaces of varying widths representing strings of binary zeros. The specific arrangement of elements defines the encoded data according to a set of rules and definitions specified by the specific type of encoding being used. The height of a one-dimensional barcode is the height of each of the parallel bars and spaces. As more information is encoded into the barcode, the barcode width changes and the barcode height stays constant. A barcode exhibiting these growth characteristics is referred to as having linear growth properties.
As noted above, the parallel bars and spaces of one-dimensional barcodes have varying widths. Generally, the bars and spaces can be no smaller than a specified minimum width termed the barcode's "x dimension". While the theoretical minimum "x dimension" size is the wavelength of the light being used to read the barcode, other practical limitations exist. Among these limitations are the desired depth of field of the reading equipment, the limitations of a given printing process and the robustness of the printed image to be correctly read despite dust, dirt, and minor physical damage. The relative size of the bars and spaces is determined by the type of coding use. The number of characters per unit length represented by the barcode symbol is referred to as the density of the symbol.
To encode a desired sequence of characters, a collection of element arrangements are concatenated together to form the complete barcode symbol, with each character of the message being represented by its own corresponding group of elements. In some symbologies, a "start" and "stop" character is used to indicate where the barcode begins and ends. A limitation of barcodes that use start and stop patterns is that these patterns take up wasted space because they are not used to encode any data.
Because most one-dimensional codes can get unusably long as lengthy data strings are encoded, most one-dimensional barcodes contain only five or six letters or digits. In view of the relatively small amount of data contained in a typical one-dimensional barcode, the most typical applications of a one-dimensional barcode is to use the encoded data merely as an index to a file or data base associated with the computer system where more comprehensive information is available. A number of different one-dimensional barcode symbologies exist including UPC/EAN, Coder 39, Code 93, Code 128, and Interleaved 2 of 5.
There are multiple variations of two-dimensional barcodes that currently exist. As for one-dimensional codes, two-dimensional codes can either printed directly on an object or on labels that are affixed to the object. One such two-dimensional barcode variation is an extension of a one-dimensional barcode in that one-dimensional barcodes are stacked with horizontal guard bars between them to increase the density. An example of such a barcode is shown in U.S. Pat. No. 4,794,239 to Allais. Other two-dimensional codes do not require a guard bar.
An example of a barcode not requiring a guard bar can be seen in U.S. Pat. No. 5,304,786 to Pavlidis et al and is referred to as PDF417 and is shown in FIG. 3. The '786 patent eliminates the use of guard bars by having data values (codewords) in alternating rows being selected from mutually exclusive subsets of bar and space patterns. The subsets are defined in terms of particular values of discriminator function which is a function of the bar and space pattern in a given codeword. Alternating rows of bar and space patterns selected from mutually exclusive subsets of bar and space patterns allows the scanner to recognize whether a scan line has crossed a row in the middle of a codeword, because if a row has been crossed, the codewords scanned will not yield the same discriminator value as the previous row.
A limitation of two-dimensional barcodes which are comprised of a plurality of stacked one-dimensional codes is that they are sensitive to printing variations. This limitation occurs because the relative widths of the bars and spaces determine the data encoded in the barcode and any variation thereof will cause data errors to be incurred when scanning. The '786 patent also discloses the broad concept of using codewords of different colors in alternate rows. That is, all rows of a multi-row label could use the same subset of bar and space patterns as codewords, but in different colors; the determination whether a row has been crossed would be made based on whether a color change had occurred.
Another type of two-dimensional barcode that exists is one containing a matrix of cells. The matrix has a respective width and height. DATA CODE is an example of this type of barcode and is shown in FIG. 4. These types of codes currently are formed under an invisible square grid. Cells under the grid are selectively darkened to be read by an optical scanning device. Decoding two-dimensional barcodes composed out of a matrix of cells is performed by laying down an imaginary grid over the matrix of cells and sampling over each grid center to determine if each cell is darkened or not darkened. Depending on the specification for the code, certain combinations of cells being darkened and other cells not being darkened can be translated by the optical scanning device into numeric or character data depending on the specification for the barcode.
Most two-dimensional barcodes are capable of storing much more information than one-dimensional barcodes as described in the '786 patent. The size of two-dimensional barcodes containing a matrix of cells is proportional to the amount of data being stored in the barcode. Most two-dimensional barcodes containing a matrix of cells have an equal width and height but that is not always a requirement. Other two-dimensional barcodes which are comprised of stacked one-dimensional barcodes generally do not keep their width and height constant. In the case of PDF417, the height of each stacked linear barcode is allowed to variably change at each linear row as shown in FIG. 5 where rows 1 and 2 are of different heights.
Transition barcodes encode information by inserting transition indicia between adjacent barcode elements. One such transition code is shown in FIG. 2. This barcode is a one-dimensional barcode symbology in which solid bars and spaces of specified widths are replaced by cell columns of no required width. The barcode contains a plurality of cell column combinations that are concatenated together to form the complete barcode symbol, with each character of the message being represented by its own corresponding group of cell columns. The barcode uses "start" and "stop" characters to indicate where the barcode begins and ends. Only certain cell column combinations are chosen to form the complete barcode symbol. The cell column pattern chosen to represent a data value is dependent on the cell column pattern of the previous cell column to guarantee that enough change between adjoining cell columns is present. The change between adjacent cell columns is a form of transition indicia. Because the barcode is guaranteed on having a certain amount of change between each adjoining cell column, this type of barcode can be scanned by a barcode scanner having a variable scanning rate without using an additional clock track on the barcode or a positional encoder on the barcode scanner. This can be accomplished because the change between each adjacent cell column is used to signal that the cell column has been traversed. Because of this, the barcode symbology is fairly robust against distortions caused by low quality printing process, direct marking processes and hand-held scanning with linear CCD barcode scanners as will be discussed hereinafter.
The barcode symbology of FIG. 2 can also be viewed as a two-dimensional symbology formed as a matrix of cells. As additional data is encoded in the barcode, the barcode grows in a linear direction and the height of the barcode does not change unless subjected to a printing or scanning anomaly. The barcode symbology of FIG. 2 can additionally be viewed as a sparse matrix symbology where there is guaranteed absence of cells in the symbology depending on the data being encoded. This absence of cells coupled with the data encoding specification for the barcode is a form of transition indicia and aids in distortion resistance.
Another type of transition code can be found in U.S. Pat. No. 3,637,993 to Christie et al and is shown in FIG. 6. The '993 patent discloses a linear barcode comprised of a plurality of contiguous colored bars, where each colored bar is of a color different from the color of its neighboring color bars. FIG. 6 shows an embodiment of this prior art barcode having three different colored bars 4, 5 and 6. The color change between adjacent colored bars is a form of transition indicia. Like the barcode of FIG. 2, this type of barcode can be scanned by a barcode scanner having a variable scanning rate without using an additional clock track on the barcode or a positional encoder on the barcode scanner. This barcode has the advantage of being distortion resistant and is approximately half the size of a similar color barcode having an integrated clock track. However, because the barcode is linear, the data encoding capacity of the barcode is limited and the barcode does not contain any means for error detection and correction as described next.
To resist against damage, one-dimensional, two-dimensional, and transition codes can contain error detection and error correction check-digits. One well known method for performing error detection and error correction is to use Reed-Soloman encoding and decoding and is described in U.S. Pat. No. 5,479,515 to Longacre Jr. Some linear barcodes and most two-dimensional barcodes and transition barcodes use Reed-Soloman encoding.
Reed-Soloman encoding requires the use of check-digits to be appended to the data portion of the barcode symbology. If a group of barcode elements (cells or bar and space patterns) in any type of barcode symbology that forms a single data value is damaged, error detection and correction check-digits will detect the error and correct the error. This is referred to as single or level error correction. The number of errors that can be corrected is proportional to the number of check-digits present in the symbology. Often times, additional check-digits are used to diminish the possibility of misdecodes. These additional check-digits can either be additional Reed-Soloman check-digits or Cyclic Redundancy Check digits.
In existing two-dimensional matrix type barcodes and transition barcodes, a grouping of cells is generally used to represent one data value. Traditionally, if one cell out of that group of cells is damaged, the data value assigned to that group of cells cannot be determined. As previously discussed, however, the data value associated with that group of cells can be detected and corrected by the error detection and correction check-digits.
It is a continuous goal to improve the error correction capability of any barcode symbology. To the inventors' knowledge, single level error correction has only been done. The present invention improves data correcting capability by creating cell groups that are either self-correcting or yield a restricted set of possible solutions in absence of any error correcting or error detecting digits. This type of error correction system of the present invention is defined to be double level error correction.
Distortions common among printing and hand-held scanning devices include wave, shear, scale and perspective and combinations thereof. Any of these distortions can be oriented in the horizontal or vertical direction and be uniform or non-uniform in nature. A consistent three word naming system is used to classify distortion types. The first term explains the consistency of the code and is always uniform or non-uniform. The second term describes the major axis or the distortion and is always either horizontal or vertical. The final term describes the distortion type and is either wave, shear, scale or perspective. For example, codes could be named uniform vertical wave, or non-uniform horizontal shear. This allows a consistent language to describe the distortions, and nearly any imaginable mutation of a barcode can be described by the composition of one or more of these distortion types. Non-uniform distortions simply indicate that a distortion is not consistent across the major axis listed in the distortion naming description.
A first type of distortion is perspective distortion or sometimes referred to as a projection distortion. Perspective distortion is generally caused by an artifact in the scanning system where the imaging plane of the scanner is not placed parallel to the image plane of the barcode being scanned. Perspective distortion can either be uniform or non-uniform in nature. Uniform perspective distortion can be horizontal or vertical as shown in FIGS. 7 and 8, respectively. An example of non-uniform horizontal and vertical perspective distortion is shown in FIGS. 26 and 27, respectively.
Existing one-dimensional barcode symbologies can be difficult to decode under uniform perspective distortions because the relative spacing of bars and spaces is not preserved as shown in FIG. 13. The exception to this is when CCD two-dimensional scanners are used where the magnitude of perspective distortion can be calculated and the perspectively distorted scanned image can then be corrected. When decoding two-dimensional matrix symbologies, a grid is constructed over the symbology as described previously except the grid is uniformly scaled to fit over the perspectively distorted image. Unfortunately, this process is computationally intensive, requires extensive computer processing power, and takes time to perform. Transition symbologies, like the barcode of FIG. 2, can generally be easily decoded under uniform perspective distortions but, at times, require some processing to determine the extent and parameters of the perspective distortion. Transition barcodes as disclosed in the '993 patent are not affected by perspective distortions.
A second type of distortion is scaling distortion. Scaling distortions can be caused by errors in the printing system or caused by artifacts in the scanning system. Scaling distortions can uniformly occur over both the horizontal and vertical axis as shown in FIGS. 9 and 10, respectively, and can be non-uniformly distributed over the horizontal and vertical axis as shown in FIGS. 11 and 12, respectively.
Most linear barcode symbologies are not affected by uniform scaling distortions because the relative size of the bars and spaces remain constant. However, some linear barcode symbologies, like UPC, require that the barcode be of a specific length. Uniform horizontal scaling distortions would cause the overall linear barcode length to shrink or expand rendering a barcode, like the UPC symbology, to be out of tolerance and, likewise, unscannable. Two-dimensional barcode symbologies are not affected by uniform horizontal or vertical scaling distortions unless the distortions causes the element sizes or the aspect ratio of the code to exceed the maximum specified for that specific barcode symbology. Because all transition codes in the '993 patent have no aspect ratio requirements or element size restrictions, they are not rendered unscannable under uniform horizontal or vertical scaling distortions.
Linear barcode symbologies are not affected by non-uniform vertical scaling distortions as the appearance of the bars and spaces would not change. However, non-uniform horizontal scaling distortions are disastrous to linear barcode symbologies as the relative sizes of the bars and spaces will change rendering the barcode unreadable as shown in FIG. 14. The exception to this are linear barcodes having clock tracks formed within, such as the barcode known as Postnet. These types of linear barcodes can be non-uniformly horizontally distorted and still be scanable.
As for linear barcode symbologies, linear stacked two-dimensional symbologies are most affected by non-uniform horizontal scaling distortions as the relative sizes of the bars and spaces will change causing the barcode to be unscannable.
Generally, two-dimensional matrix symbologies are more tolerant of non-uniform scaling distortions across any major axis. Decoding two-dimensional matrix symbologies having non-uniform horizontal or vertical scaling distortions requires that an imaginary grid be non-uniformly distorted in the same fashion as the distorted barcode and placed over the distorted barcode. Forming a non-uniformly distorted imaginary grid is difficult to do in absence of any indicia on the barcode to indicate how the barcode is non-uniformly distorted. Clock tracks are often added to two-dimensional matrix symbologies to aid in forming this imaginary grid but with any major scaling distortions will still render these codes unscannable. In addition, mathematically forming a non-uniformly distorted imaginary grid is time consuming and requires a substantial amount of computing capability.
All existing transition codes are highly resistant to all types of non-uniform horizontal and vertical scaling distortions because varying element widths and heights does not affect the decodability of the code as a result of the presence of transition indica inherent in the symbology. Examples of the transition code of FIG. 2 being subjected to non-uniform horizontal and vertical scaling distortion may be found in FIGS. 15 and 16, respectively.
A third type of distortion is shear distortion. This type of distortion is often caused by the elements of a printhead not being exactly perpendicular to the direction of movement of the substrate being marked. Shear distortion can be created as an artifact of the scanning apparatus. For example, FIG. 25 shows a hand-held, one-dimensional scanning apparatus 7 scanning a non-distorted barcode 8 on a piece of paper. The scanning apparatus 7 will view the barcode 8 as having a shear distortion if axis 9 of the scanning elements of the scanning apparatus 7 is not perpendicular to the major axis 10 of the barcode 8 being scanned.
FIG. 17 shows an example of uniform horizontal shear distortion and FIG. 18 shows an example of uniform vertical shear distortion. All barcode types are generally resistant to mild forms of uniform shear distortion. However, excessive amounts of this distortion will render most existing barcode symbologies unscannable except the color transition code disclosed in the '993 patent. Scanning under severe shear distortions becomes difficult because bar and space widths become difficult to determine in linear and stacked two-dimensional symbologies and element locations in two-dimensional matrix symbologies also become difficult to determine without extensive processing. Transition codes, such as the barcode of FIG. 2, are more tolerant of uniform shear distortions but they can become very difficult to decode under severe shear distortions because the transition point of each cell column becomes difficult to determine. The color transition barcode disclosed in the '993 patent is not affected by uniform shear distortions because the intersection angle between each adjoining colored bar changes but does not affect scanability.
Non-uniform horizontal and vertical shear distortions as shown in FIGS. 19 and 20, respectively, are disastrous for all existing types of barcodes because the positions and relative spacing of the elements of these barcodes cannot be reliably determined. There are two exceptions however. The color transition barcode disclosed in the '993 patent is not affected by non-uniform shear distortions because the intersection angle between each adjoining colored bar changes but does not affect scanability. The transition code of FIG. 2 is resistant to small amounts of this type of non-uniform shear distortion but excessive amounts of this distortion type will render this barcode unscannable because the transition point of each cell column becomes impossible to determine.
Referring again to FIG. 25, non-uniform horizontal and vertical shear distortions are most commonly caused by artifacts of the scanning process when the longitudinal axis 9 of the scanning elements of the hand-held barcode scanner 7 variably change in relationship to the major axis 10 of the barcode 8 being scanned. This can occur when the hand-held barcode scanner 7 is rotated around its longitudinal axis 11 as the barcode 8 is being scanned.
The last type of barcode distortion is wave distortion. Wave distortion can occur over the horizontal or vertical axis of a barcode and can be both uniform and non-uniform in type. Wave, in the context of this disclosure, implies a disturbance or oscillation between two points across the barcode in the direction parallel to the major axis of distortion. The disturbance or oscillation can be any type, such as sinusoidal, triangle, square, or saw. FIGS. 21 and 22, show examples of both uniform horizontal and vertical distortions having a sinusoidal waveform type. One characteristic attribute of uniform wave distortion is that the wave type is the same magnitude and phase on each end of the barcode. Non-uniform horizontal and vertical wave distortions shown in FIGS. 23 and 24, respectively, do not have the same magnitude and phase on each opposing end of the barcode.
Wave distortions can occur during the printing process where the object being marked moves relative to the printing apparatus. Wave distortions can be caused by an artifact of the scanning system. Referring again to FIG. 25, ideally, the barcode scanner 7 should not move along axis 12 of barcode 8 and only travel along the major axis 10 of barcode 8. Uniform wave distortions will be created if the hand-held scanner 7 begins to oscillate along axis 12 as the barcode is being scanned along axis 10.
Linear barcodes are very tolerant of uniform horizontal wave distortions. However, they are not very tolerant of uniform vertical wave distortions because a scanner may perceive improper bar and space widths if the barcode scanner is not scanning exactly parallel to the axis of the barcode being scanned.
Two-dimensional barcodes are not tolerant of any type of wave distortion as attempting to compute an imaginary grid over the barcode symbology to decode it is time consuming, requires a substantial amount of computing power and may be impossible without the aid of any suitable indicia from the barcode symbology indicating how the barcode is wave distorted. Barcode finder patterns and clock tracks help but under any substantial wave distortion, these indicia are generally not sufficient.
Transition codes, such as the barcode of FIG. 2, are extremely tolerant of uniform horizontal wave distortion. However, transition indica becomes lost under the remaining types of wave distortions and, likewise, the barcode of FIG. 2 becomes increasingly difficult to decode under these types of distortions. The color transition code disclosed in the '993 patent and shown in FIG. 6, would be resistant to any type of uniform or non-uniform wave distortion because no transition indicia is lost under any type of wave distortion.
A propagation error in a barcode symbology occurs when an error in one element of the barcode propagates to the next or preceding element of the barcode. Therefore, one error becomes two or more errors. This phenomenon generally is caused by elements values of a barcode symbology being dependent on the value or structure of an adjacent element. The barcode of FIG. 2 is one example of a barcode symbology that is subject to propagation errors.
Propagation errors can also occur in color barcodes. U.S. Pat. No. 5,576,528 to Chew et al. describes a method for increasing information density of a barcode symbology by generating multiple constituent barcode symbols where each symbol is formed in a different color selected from a group of various primary colors. Each colored symbol is then overlaid on top of each other thus forming an aggregate barcode symbol of various colors. In areas where the differently colored bars overlap each other, colors distinct from those in the original group of colors are formed. Using a reverse process, each individual barcode can then be separated and individually processed.
Although this encoding method increases information density, robustness of the aggregate barcode symbology decreases as a result of propagation error phenomenon. This occurs because an error or color change in one element of the barcode may, under most circumstances, prevent the remaining color layers of the barcode from being determined.
The only barcode symbology that exhibits extraordinary resistance to all types of damage and distortions and is not subject to propagation errors is the color transition barcode disclosed in the '993 patent. This barcode, however, is limited in its data capacity, does not contain a space efficient data encoding method, and does not contain any means for error correction and detection.
Distortion and damage resistance is very important in barcode symbologies when using hand-held printers and hand-held scanners because the human hand tends to be unsteady which can cause variations in the printing and scanning processes. A barcode having inherent distortion resistance is easier and quicker to scan with area and linear barcode scanning devices.
Damage and distortion resistance is also important when low quality printing processes are used, such as industrial ink-jet marking machines. Providing high quality marking and scanning machines is expensive and unnecessary if the barcode symbology being used is highly distortion resistant and contains a substantial amount of error detection and correction means. Distortion resistance is also important for most types of scanning applications because artifacts of the scanning system can cause the barcode to appear distorted.
With inexpensive color printing and scanning means becoming more prevalent, using color information in a barcode symbology is not unreasonable and quite desirable because color information, when used properly, aids in damage and distortion resistance while increasing the informational density of the barcode. Color is also eye appealing and desirable for marking consumer goods.
For the foregoing reasons, there is a need for a color transition barcode symbology that is resistant to the effects of all types of damage and distortions discussed hereinabove coupled with a space-efficient data encoding structure, and double error correction capability.